package ysf.com.sort;

import com.alibaba.fastjson.JSON;

/**
 * @author ysf
 * @version 1.0
 * @date 2021/12/11 15:00
 * <p>
 * 堆排序
 */
public class HeapSort {


    public static void main(String[] args) {

        int[] arrys = {9, 1, 10, 5, 6, 3, 4};
        System.out.println(JSON.toJSONString(arrys));
        hearSort(arrys);
        System.out.println(JSON.toJSONString(arrys));

    }

    /**
     * 堆排序
     *
     * @param arrys 待排序的整型数组
     */
    public static void hearSort(int[] arrys) {

        // 开始位置是最后一个非叶子节点，即最后一个结点的父结点
        int start = (arrys.length - 1) / 2;

        // 调整为大顶堆
        for (int i = start; i >= 0; i--) {

            maxHeap(arrys, arrys.length, i);
        }

        // 先把数组中第 0 个位置的数和堆中最后一个数交换位置，再把前面的处理为大顶堆
        for (int i = arrys.length - 1; i > 0; i--) {

            int temp = arrys[0];
            arrys[0] = arrys[i];
            arrys[i] = temp;
            maxHeap(arrys, i, 0);

        }

    }

    /**
     * 转化为大顶堆
     *
     * @param arrys 待排序的数组
     * @param size  待调整的区间长度
     * @param index 节点下标
     */
    public static void maxHeap(int[] arrys, int size, int index) {
        // 左子结点
        int leftNode = 2 * index + 1;
        // 右子结点
        int rightNode = 2 * index + 2;
        int max = index;

        // 和两个子结点分别对比，找出最大的结点
        if (leftNode < size && arrys[leftNode] > arrys[max]) {
            max = leftNode;
        }
        if (rightNode < size && arrys[rightNode] > arrys[max]) {
            max = rightNode;
        }
        // 交换位置
        if (max != index) {
            int temp = arrys[index];
            arrys[index] = arrys[max];
            arrys[max] = temp;
            // 因为交换位置后有可能使子树不满足大顶堆条件，所以要对子树进行调整
            maxHeap(arrys, size, max);
        }

    }


}
